from typing import List


class Solution:
    def maximumTastiness(self, price: List[int], k: int) -> int:
        price.sort()
        left = -1
        right = price[-1] - price[0] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if self.check(price, k, mid):
                left = mid
            else:
                right = mid
        return left

    def check(self, price: List[int], k: int, mid: int):
        ret = []
        for i in price:
            if not ret:
                ret.append(i)
                continue
            if i - ret[-1] >= mid:
                ret.append(i)
        return len(ret) >= k

